﻿#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    int dp[60][2];
    int dfs(int cnum, bool firstDecompose) {
        if (cnum == 1) return 1;
        if (dp[cnum][firstDecompose] != -1) return dp[cnum][firstDecompose];
        int maxans = 0;
        for (int i = 1; i < cnum; i++) {
            int nnum = cnum - i;
            int cret = dfs(nnum, false);
            int cans = cret * i;
            maxans = max(maxans, cans);
        }
        if (!firstDecompose)
            maxans = max(maxans, cnum);
        return dp[cnum][firstDecompose] = maxans;
    }
public:
    int integerBreak(int n) {
        memset(dp, -1, sizeof(dp));
        return dfs(n, true);
    }
};

int main() {
    Solution solution;
    int n = 10;
    cout << solution.integerBreak(n) << endl;
    return 0;
}